NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/640

Internet Message Format | 1996-08-06 | 2KB

Path: hubcap.clemson.edu!hubcap!mjs
From: [e-mail] (M. J. Saltzman)
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: 21 Mar 96 14:53:18 GMT
Organization: Clemson University
Message-ID: <mjs.827419998@hubcap>
References: <4iokop$[e-mail]>
NNTP-Posting-Host: hubcap.clemson.edu
X-Newsreader: NN version 6.5.0 #1

[e-mail] (James Bonfield) writes:

|Are there any limitations on what the sort function passed over to qsort can
|do or return? I know it's meant to return < 0, 0 or > 0 for the various
|compare operations, but which you return is purely up to your own comparison
|system.

|On tracking down a bug in some old code I noticed that we had the
|compare function returning something like "a > b" instead of "b - a".
|Now this is obviously some silly bug in our coding, but "a > b" is still
|a valid sort function surely? The reason I ask is that this that such
|functions appear to make the Irix 5.3 qsort() function underflow the
|passed array. Please check the following function to verify that I
|haven't done something daft.

As others have pointed out, b - a runs the risk of overflow if a and b
are large enough in magnitude and of opposite sign.  That's why it is
often recommended against as a value to return from the compare function.
BTW, without overflow, b - a is positive if b > a, not if a > b.


|#include <stdio.h>
|#include <stdlib.h>

|static int sort_func(const void *pa, const void *pb)
|{
|    const int *a = (int *)pa;
|    const int *b = (int *)pb;

|    return *a > *b;
|}

This function returns either a 0 if *a <= *b or a 1 if *a > *b.  Since
keys are considered equal if sort_func() returns zero, this will not
properly discern a case where the first argument must appear before
the second.  It would surprise me not at all if qsort() relied on
sort_func() having the property that

    !!sort_func(p1, p2) == -1 * !!sort_func(p2, p1)

which does not hold for this function.  (The Standard wording seems
to me to require this property, but I'm not a duly certified language
lawyer...)

Try

    static int sort_func(const void *pa, const void *pb)
    {
        const int *a = (int *)pa;
        const int *b = (int *)pb;

        return (*a > *b) - (*a < *b);
    }

instead.
--
        Matthew Saltzman
        Clemson University Math Sciences
        [e-mail]